class Solution {
public:
    unordered_map<int, vector<int>> ma;
    double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
        if (target == 1 && n == 1) return 1;
        for (auto& x : edges)
        {
            ma[x[0]].push_back(x[1]);
            ma[x[1]].push_back(x[0]);
        }
        return dfs(1, -1, target, 1, 0, t);
    }
    double dfs(int pos, int pre, int target, double ans, int n, int t)
    {
        if (pos == target && n == t) return ans;
        else if (pos == target && n < t && ma[pos].size() == 1 && pos != 1) return ans;
        double num = 0;
        for (auto& x : ma[pos])
        {
            if (x == pre) continue;
            if (pre == -1) num = max(num, dfs(x, pos, target, ans / ma[pos].size(), n + 1, t));
            else num = max(num, dfs(x, pos, target, ans / (ma[pos].size() - 1), n + 1, t));
        }
        return num;
    }
};